import java.util.*;

public class Test2 {


    public List<String> topKFrequent(String[] words, int k) {
        //1、先统计单词出现的次数->存储到了map当中
       HashMap<String, Integer> map = new HashMap<>();
        for (String w: words) {
            if(map.get(w) == null) {
                map.put(w, 1);
            } else {
                int val = map.get(w);
                map.put(w,val+1);
            }
        }
        //2、遍历好统计好的Map，把每组数据存储到小根堆当中
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                Map.Entry<String, Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                } else {
                    if(top.getValue().compareTo(entry.getValue()) == 0) {
                        if(top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }

        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top = minHeap.poll();
            ret.add(top.getKey());
        }

        Collections.reverse(ret);

        return ret;
    }
    public static  boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) return false;

        HashMap<Character, Character> map = new HashMap<>();
            map.put(')','(');
            map.put('}','{');
            map.put(']','[');

        Deque<Character> stack = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if(map.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != map.get(ch)) {
                    return false;
                }
                stack.pop();
            }
            stack.push(ch);
        }

        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String str = "()[]{}";
        boolean valid = isValid(str);
        System.out.println(valid);
    }

}
